# Pixels and images

Pixel stands for picture element.  Any image (picture) on a computer is made up of a grid of pixels arranged in rows and columns:

{bmc A-lo-large.bmp} Enlarged 	Normal {bmc A-lo-small.bmp}

Each square pixel holds a single color or shade of grey.  The number of pixels determines an image’s dimensions: the above image is 16x16, because it has 16 columns and 16 rows.  How large the pixels are determines the image’s resolution: how finely detailed the image is.

{bmc A-hi-large.bmp} Enlarged 	Normal size {bmc A-hi-small.bmp}

Here we have doubled the image’s resolution, and the image looks better as a result.  Because the image is the same size, the image’s dimensions have also been doubled to 32x32.

# Frames and framerates

Digitally stored video consists of a series of images, or frames.  By playing a series of frames in sequence like a flipbook, we can simulate motion:

{bmc frames.bmp}

The speed at which successive frames are played is measured in frames per second (fps).  The more frames per second, the smoother the video is; professional movies are filmed at 24 or 48 fps, and television runs at 25 or 30 fps.  Because high framerates take a lot of space for all the individual frames, a lot of computer video only runs at 10 or 15 frames per second, which may look a bit jerky to some people.

# Keyframes vs. delta frames

Playing a bunch of individual frames is fine, but it’s a lot of trouble to keep track of all the separate frames.  For instance, take these two frames:

{bmc delta-frame1.bmp} {bmc delta-frame2.bmp}

The only difference between these two frames is that the red A moved down and to the right, and yet we have to store the whole picture for both frames -- including the blue triangle and green square which don’t change.  But what if we stored the frames like this:

{bmc delta-frame1.bmp} {bmc delta-framediff.bmp}

The first frame hasn’t changed, but instead of storing the second frame, we make a delta frame that only stores the differences between the two frames, and store the delta frame instead.  Now the second frame only takes up a tiny bit of space, because only a small part of the frame changed.  The first frame is now a keyframe, because it is the key to decoding the second.  When we add a third frame, we can do the same trick and store the differences between the second and third frames.

So what’s the drawback to delta frames?

{bmc keyframes.bmp}

The drawback is that to decode a delta frame, we need to have the frame before it.  But if that frame is also a delta frame, we need to know the frame before that, and so on.  In fact, we’d need to go all the way to the last keyframe, and start decoding delta frames one-by-one until we got to the frame we wanted.  For instance, let’s say we wanted frame 8.  Frame 8 is a delta frame, so we need to decode frame 7.  Frame 7 is also a delta frame, so we need 6.  We’d need to decode frames 1-6 before we could get to frame 7.  There’s another keyframe at frame 10, though, so if we needed frame 12, only 10 and 11 would need to be fetched.  We can reduce the problem by putting in keyframes more often, but keyframes are usually bigger, and so our video file would get bigger as well.  Most video files have keyframes every 5-30 frames.

There’s another reason to watch the keyframe interval.  Delta frames aren’t normally stored exactly; they approximately reconstruct the original frame.  This saves a lot of space, because tiny details that take up a lot of space can be tossed.  Unfortunately, this sometimes means that the image degrades as more and more delta frames are generated, and so the longer the keyframe interval, the worse the image gets between keyframes.

# It all seems so big…

…and it is.  Raw, uncompressed video takes anywhere from 1-3 bytes per pixel, and so a single 320x240 frame takes from 77K to 230K of space.  16-bit uncompressed video is common and takes 2 bytes per pixel, so that’s a whopping 2.3 megabytes of space per second.  That’s a ton of space!

There are three ways to save space.  The first is to shrink the picture.  Shrinking a video file from 320x240 to 160x120 makes it look half-size (or half-resolution) and so it doesn’t look as good.  But you have half the columns and half the rows, so it actually takes one-fourth the space.  Unfortunately, it also works the other way around: ‘doubling’ the size to 640x480 takes four times the space.  Nowadays, any reducing video below 240x180 is usually too small to use, and 320x240 or 352x240 is the norm.  Above 320x240, video very quickly takes too much space and computing power to process.  There is no way you’re going to store your full-screen 800x600 Quake II game on disk as a video file.

The second is to reduce the framerate.  There are no tricks here; half the framerate leads to half the data.  However, the more you reduce the framerate, the more quickly people notice.  People won’t notice if you drop half the frames in a 30fps video and make a 15fps one instead.  But they’ll cry murder if you drop half the frames again and make a 7.5fps video.  You can’t cleanly drop the framerate by a fraction; for instance, reducing a 15fps video to 10fps doesn’t work so well because you have to drop one frame out of every three, making a jerky video.  The best solution is simply to figure what framerate you want, and work at that framerate to begin with.

The third is compression.  We’ll cover that next.

# Video compression

You can’t take raw video and throw it through ZIP or RAR.  Regular compression algorithms are lossless and have to give back exactly what they packed; it would be very bad if a program file came out different than when it went in.  But lossless compression doesn’t work for video; even though your eye can’t tell the difference, there’s often a little noise or tiny details that the computer knows about.  Lossless compression algorithms usually can’t pack video down to less than one-half original size.

The solution is lossy compression; figure out what the eye doesn’t care about, and throw it away.  Then figure out the best way to store what’s left.  Instead of one-half, we can now compress down to one-tenth to one-twentieth original size.  The decompressed picture doesn’t exactly match the original, but it’s close enough and so much smaller than basically every video compression algorithm is lossy, including Intel Indeo, MPEG, Cinepak, Sorenson, and MJPEG.

There’s another big advantage to lossy compression: you can control how big you want the video file, by controlling how much data is thrown out.  Of course, the more you compress, the lousier the data looks.  At a certain point, more compression isn’t worth it, because reducing the video size by even 10% makes it look 10 times worse.  The compression artifacts that result from high levels of compression vary from algorithm to algorithm.  Some methods cause the picture to get blurry, and others add edges and specks to the picture.

One quick note: sometimes you’ll see MPEG advertised as getting 100:1 or similar ridiculous compression ratios.  This is complete B.S.; realistic ratios for MPEG are around 26:1, according to people who created the MPEG standard.  Real 100:1 compression results in video that looks more like colored bathroom tiles.

# Compression artifacts

You’ve taken a 100Mb raw video masterpiece, and packed it down into a 5Mb file using Intel Indeo or some other compression codec.  When you play it back, though, some parts are too blurry to see, and other areas have blocky edges, and large, flat gradients have stairsteps on them.  What happened?

The compression algorithm threw out a bit too much data.  The codec couldn’t store all the information about the gradients, edges, and shapes in the picture, so it started discarding parts of the picture until it could.  All of the artifacts in the compressed video are a result of this discarding.

Blurriness

Blurring an image simplifies it, because sharp details become smooth shapes and curves.  As a result, when a compression algorithm is short on space, it usually tries to figure out which details in the picture are the most important and should be saved, and blurs less important details.  If a particular spot in the picture frame has sharp details but doesn’t change for several seconds, some compression algorithms will figure that out and only encode the details once.  But if that spot moves, the algorithm might not be able to efficiently detect or store the movement, and just blurs it instead.

Stairstepping and blockiness

{bmc blocky-before.bmp} {bmc blocky-after.bmp}

What happened here?  The artifacts in the compressed image are the result of tiling or blocking; most compression algorithms split the picture into 4x4 or 8x8 pixel tiles to speed up compression.  Tile boundaries don’t become visible until you lower the compression quality greatly; then the compressor starts to drop so much data that adjacent tiles change very differently, resulting in a visible boundary between them.

Stairstepping is an extreme case, where the codec discards all the data about a tile except for the average color of all the pixels in the tile, reducing any detail in the tile down to a flat block of color.  Large, flat gradients of color, like sky, tend to be reduced to blocky stairsteps at high compression ratios.